package org.example.myleet.p749;

import java.util.*;

public class Solution {

    private static final int[][] DIRECTIONS = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    private static final int DISINFECTED = 0;
    private static final int INFECTED = 1;
    private static final int INFECTED_CONTROLLED = 2;

    public int containVirus(int[][] isInfected) {
        int r = isInfected.length, c = isInfected[0].length, total = r * c;
        int totalFence = 0;
        while (true) {
            //每一回合进行整个世界的模拟
            boolean[][] visited = new boolean[r][c];
            Map<Integer, InfectedArea> infectedMapFrontiers = new HashMap<>();
            for (int i = 0; i < r; ++i) {
                for (int j = 0; j < c; ++j) {
                    if (visited[i][j]) {
                        continue;
                    }
                    if (DISINFECTED == isInfected[i][j]) {
                        //遇到未感染的位置，标记为已经访问过
                        visited[i][j] = true;
                        continue;
                    }
                    if (INFECTED_CONTROLLED == isInfected[i][j]) {
                        //遇到已经控制了感染区的地方，标记为已经访问过，并且感染位置数+1
                        visited[i][j] = true;
                        continue;
                    }
                    //不属于以上两种情况，说明是找到一个未控制的感染区
                    //记录需要增加的围栏数量
                    int frontierFenceCount = 0;
                    //记录感染区紧邻的未感染前线
                    Set<Integer> frontiers = new HashSet<>();
                    //记录感染区域的所有点
                    Set<Integer> infectedPoints = new HashSet<>();
                    //BFS用，缓存待遍历的感染区位置
                    Queue<int[]> queue = new LinkedList<>();
                    queue.add(new int[]{i, j});
                    visited[i][j] = true;
                    while (!queue.isEmpty()) {
                        int size = queue.size();
                        for (int k = 0; k < size; ++k) {
                            //访问一个感染区域，记录一个感染区位置点
                            int[] p = queue.poll();
                            infectedPoints.add(pointToKey(p[0], p[1]));
                            for (int l = 0; l < 4; ++l) {
                                //向4个方向广度搜索
                                int rNext = p[0] + DIRECTIONS[l][0];
                                int cNext = p[1] + DIRECTIONS[l][1];
                                if (0 <= rNext && rNext < r && 0 <= cNext && cNext < c) {
                                    if (DISINFECTED == isInfected[rNext][cNext]) {
                                        //记录未感染区前线，增加一个围栏
                                        ++frontierFenceCount;
                                        frontiers.add(pointToKey(rNext, cNext));
                                    } else if (INFECTED == isInfected[rNext][cNext] && !visited[rNext][cNext]) {
                                        //缓存待遍历的感染区
                                        queue.add(new int[]{rNext, cNext});
                                        visited[rNext][cNext] = true;
                                    }
                                }
                            }
                        }
                    }
                    //BFS结束，找到一个完整连接的感染区，记录到map中
                    InfectedArea infectedArea = new InfectedArea(i, j, frontierFenceCount, frontiers, infectedPoints);
                    infectedMapFrontiers.put(pointToKey(i, j), infectedArea);
                }
            }
            //找到感染前线范围最大（即题目中威胁度最大）区域
            int maxFrontierCount = 0;
            Map.Entry<Integer, InfectedArea> candidateEntry = null;
            for (Map.Entry<Integer, InfectedArea> entry : infectedMapFrontiers.entrySet()) {
                if (maxFrontierCount < entry.getValue().frontiers.size()) {
                    maxFrontierCount = entry.getValue().frontiers.size();
                    candidateEntry = entry;
                }
            }
            if (null != candidateEntry) {
                totalFence += candidateEntry.getValue().frontierFenceCount;
                for (Map.Entry<Integer, InfectedArea> entry : infectedMapFrontiers.entrySet()) {
                    if (candidateEntry.getKey().equals(entry.getKey())) {
                        //这个候选区域进行围栏围堵
                        for (Integer key : entry.getValue().infectedPoints) {
                            int[] p = keyToPoint(key);
                            isInfected[p[0]][p[1]] = INFECTED_CONTROLLED;
                        }
                    } else {
                        //其他感染区域的前线进行扩散模拟
                        for (Integer key : entry.getValue().frontiers) {
                            int[] p = keyToPoint(key);
                            isInfected[p[0]][p[1]] = INFECTED;
                        }
                    }
                }
            } else {
                //没有候选设置围栏的区域，结束搜索
                break;
            }
        }
        return totalFence;
    }

    private Integer pointToKey(int row, int col) {
        return row * 100 + col;
    }

    private int[] keyToPoint(Integer key) {
        int row = key / 100;
        int col = key % 100;
        return new int[]{row, col};
    }

    static class InfectedArea {
        int row;
        int col;
        int frontierFenceCount;
        Set<Integer> frontiers;
        Set<Integer> infectedPoints;

        public InfectedArea(int row, int col, int frontierFenceCount, Set<Integer> frontiers, Set<Integer> infectedPoints) {
            this.row = row;
            this.col = col;
            this.frontierFenceCount = frontierFenceCount;
            this.frontiers = frontiers;
            this.infectedPoints = infectedPoints;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("InfectedArea{");
            sb.append("row=").append(row);
            sb.append(", col=").append(col);
            sb.append(", frontierFenceCount=").append(frontierFenceCount);
            sb.append(", frontierSize=").append(frontiers.size());
            sb.append('}');
            return sb.toString();
        }
    }
}
